#ifndef SORTING_H_
#define SORTING_H_
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template<typename Comparable>
bool isSorted(vector<Comparable>& a,int left,int right)
{
    for(int i=left;i<right-1;i++)
    {
        if(a[i]>a[i+1])
            return false;
    }
    return true;
}
template <typename Comparable>
void percDown(vector<Comparable> & a,int i,int n)
{
    int child;
    Comparable tmp;           
    for(tmp=move(a[i]);2*i+1<n;i=child)
    {
        child=2*i+1;
        if(child!=n-1&&a[child]<a[child+1])
            ++child;
        if(tmp<a[child])
            a[i]=move(a[child]);
        else
            break;
    }
    a[i]=move(tmp);
}
template <typename Comparable>
void heapsort(vector<Comparable>& a)
{
    for(int i=a.size()/2-1;i>=0;--i)
        percDown(a,i,a.size()); ///建堆
    for(int j=a.size()-1;j>0;--j)
    {
        swap(a[0],a[j]);   ///把堆尾和堆首互换
        percDown(a,0,j);        ///然后再下沉，j+1以后的元素不做处理
    }
}


template <typename Comparable>
const Comparable & median3( vector<Comparable> & a, int left, int right )
{
    int center = ( left + right ) / 2;
    
    if( a[ center ] < a[ left ] )
        swap( a[ left ], a[ center ] );
    if( a[ right ] < a[ left ] )
        swap( a[ left ], a[ right ] );
    if( a[ right ] < a[ center ] )
        swap( a[ center ], a[ right ] );

        // Place pivot at position right - 1
    swap( a[ center ], a[ right - 1 ] );
    return a[ right - 1 ];
}

template <typename Comparable>
void insertionSort( vector<Comparable> & a, int left, int right )
{
    for( int p = left + 1; p <= right; ++p )
    {
        Comparable tmp = move( a[ p ] );
        int j;

        for( j = p; j > left && tmp < a[ j - 1 ]; --j )
            a[ j ] = move( a[ j - 1 ] );
        a[ j ] = move( tmp );
    }
}

/**
 * Internal quicksort method that makes recursive calls.
 * Uses median-of-three partitioning and a cutoff of 10.
 * a is an array of Comparable items.
 * left is the left-most index of the subarray.
 * right is the right-most index of the subarray.
 */
template <typename Comparable>
void quicksort( vector<Comparable> & a, int left, int right)
{
    if(isSorted(a,left,right))
        return;
    if( left + 10 <= right )
    {
        const Comparable & pivot = median3( a, left, right );

            // Begin partitioning
        int i = left, j = right - 1;
        for( ; ; )
        {
            while( a[ ++i ] < pivot ) { }
            while( pivot < a[ --j ] ) { }
            if( i < j )
                swap( a[ i ], a[ j ] );
            else
                break;
        }

        swap( a[ i ], a[ right - 1 ] );  // Restore pivot

        quicksort( a, left, i - 1 );     // Sort small elements
        quicksort( a, i + 1, right );    // Sort large elements
    }
    else  // Do an insertion sort on the subarray
        insertionSort( a, left, right );
}

/**
 * Quicksort algorithm (driver).
 */
template <typename Comparable>
void quicksort( vector<Comparable> & a )
{
    quicksort( a, 0, a.size( ) - 1 );
};

#endif